/**
 * 
 */
package calculation.passed2;

import java.util.HashMap;
import java.util.Map;

/**
 * @author xyyi
 *
 */
public class MultiplyStrings {
	/**
	Given two numbers represented as strings, return multiplication of the numbers as a string.

	Note: The numbers can be arbitrarily large and are non-negative.
	 */
	// MSD at position 0;
    public String multiply3(String num1, String num2) {
        byte[] product = new byte[num1.length() + num2.length()];
        for (int i1 = num1.length() - 1; i1 >= 0; i1--) {
            for (int i2 = num2.length() - 1; i2 >= 0; i2--) {
                int index = i1 + i2 + 1; //pitfall additional 1
                //  product[index] =  product[index] + instead of  product[index] =
                product[index] = (byte) (product[index] + (num1.charAt(i1) - '0') * (num2.charAt(i2) - '0'));
                //  product[index - 1] =  product[index - 1] + instead of  product[index - 1] =
                product[index - 1] = (byte) (product[index - 1] + product[index] / 10);
                product[index] = (byte) (product[index] % 10);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        // pitfall: special case 0
        for (int i = 0; i < product.length - 1; i++) {
            if (sb.length() == 0 && product[i] == 0)
                continue;
            sb.append(product[i]);
        }
        sb.append(product[product.length - 1]);
        return sb.toString();
    }	
    
    public String multiply2(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] product = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int index = len1 + len2 - i - j - 2;
                product[index] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                product[index + 1] += product[index] / 10;
                product[index] %= 10;
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = product.length - 1; i > 0; i--) {
            if (stringBuilder.length() == 0 && product[i] == 0)
                continue;
            stringBuilder.append(product[i]);
        }
        stringBuilder.append(product[0]);
        return stringBuilder.toString();
    }
	
	public String multiply(String num1, String num2) {
		if (num1 == null || num2 == null || num1.isEmpty() || num2.isEmpty())
			return "0";

		byte[] n1 = convertToBytes(num1);
		byte[] n2 = convertToBytes(num2);
		byte[] product = new byte[n1.length + n2.length];
		for (int i1 = n1.length - 1; i1 >= 0; i1--) {
			byte carry = 0;
			for (int i2 = n2.length - 1; i2 >= 0; i2--) {
				byte number = (byte) (n1[i1] * n2[i2] + product[i1 + i2 + 1] + carry);
				product[i1 + i2 + 1] = (byte) (number % 10);
				carry = (byte) (number / 10);
			}
			if (carry > 0) {
				product[i1] = (byte) carry;
			}
		}
		int start = 0;
		while (start < product.length && product[start] == 0)
			start++;
		if (start == product.length)
			return "0";

		StringBuilder sb = new StringBuilder();
		for (int i = start; i < product.length; i++) {
			sb.append(product[i]);
		}

		return sb.toString();
	}

	private byte[] convertToBytes(String num) {
		byte[] result = num.getBytes();
		for (int i = 0; i < result.length; i++) {
			result[i] -= '0';
		}
		return result;
	}

	public String multiply1(String num1, String num2) {
		if (num1.isEmpty() || num2.isEmpty()) {
			return "0";
		}

		num1 = new StringBuffer(num1).reverse().toString();
		num2 = new StringBuffer(num2).reverse().toString();

		StringBuffer sb = new StringBuffer();
		for (int i = 0, size = num1.length() + num2.length(); i < size; i++)
			sb.append(0);

		for (int i1 = 0; i1 < num1.length(); i1++) {
			int digit1 = num1.charAt(i1) - '0';
			int carry = 0;
			for (int i2 = 0; i2 < num2.length(); i2++) {
				int digit2 = num2.charAt(i2) - '0';
				int currDigit = sb.charAt(i1 + i2) - '0';
				int number = digit1 * digit2 + currDigit + carry;
				sb.setCharAt(i1 + i2, Character.forDigit(number % 10, 10));
				carry = number / 10;
			}
			if (carry >= 0) {
				sb.setCharAt(i1 + num2.length(), Character.forDigit(carry, 10));
			}
		}
		sb.reverse();
		int start = 0;
		while (start < sb.length() && sb.charAt(start) == '0') {
			start++;
		}
		if (start == sb.length())
			return "0";

		return sb.substring(start);
	}

	/**
	 * 
	 */
	public MultiplyStrings() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MultiplyStrings ms = new MultiplyStrings();
		String num1 = "98";
		String num2 = "9";
		System.out.println(ms.multiply(num1, num2));
		Map<Integer, String> map = new HashMap<>();
		Map.Entry<String, String> e;
	}

}
